package leetcode_900;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *@author 周杨
 *FindAndReplacePattern_890 字符匹配
 *describe:常规map遍历 AC 93%
 *2018年11月11日 下午9:00:43
 */
public class FindAndReplacePattern_890 {
	public static void main(String[] args) {
		FindAndReplacePattern_890 test=new FindAndReplacePattern_890();
		System.out.println(test.findAndReplacePattern(new String[] {"badc","abab"
				,"dddd","dede","yyxx"}, "baba").size());
	}
	
	public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> res=new ArrayList<String>();
        for(String word:words) {
        	if(match(word,pattern))
        		res.add(word);
        }
        return res;
    }
	
	 public boolean match(String word, String pattern) {
	        Map<Character, Character> M = new HashMap<Character, Character>();
	        for (int i = 0; i < word.length(); ++i) {
	            char w = word.charAt(i);
	            char p = pattern.charAt(i);
	            if (!M.containsKey(w)) M.put(w, p);
	            if (M.get(w) != p) return false;
	        }

	        boolean[] seen = new boolean[26];
	        for (char p: M.values()) {
	            if (seen[p - 'a']) return false;
	            seen[p - 'a'] = true;
	        }
	        return true;
	    }
}
